#include"December.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <stdbool.h>

//总体
struct December
{
    ElementType *a;
    int capacity;
    int size;
};

struct Telephone
{
    char *name;
    char *number;
};

bool IsNameEqual(void *p1, void *p2)
{
    Tel *s= (Tel *)p1;
    const char *str=(const char *)p2;
    return strcmp(s->name, str)==0;
}

bool IsNumberEqual(void *p1, void *p2)
{
    Tel *s= (Tel *)p1;
    const char *str=(const char *)p2;
    return strcmp(s->number, str)==0;
}

bool CompareName(void *p1, void *p2)
{
    Tel *s1=(Tel *)p1;
    Tel *s2=(Tel *)p2;
    return strcmp(s1->name,s2->name)>0;
}

bool GreatName(void *p1, void *p2)
{
    Tel *s1=(Tel *)p1;
    char *s2=(char *)p2;
    return strcmp(s1->name,s2)>0;
}

bool GreatName2(void *p1, void *p2)
{
    char *s1=(char *)p1;
    Tel *s2=(Tel *)p2;
    return strcmp(s1,s2->name)>0;
}

bool IsNameContains(void *p1, void *p2)
{
    Tel *s= (Tel*)p1;
    const char *str= (const char*)p2;
    if(strstr((const char *)(s->name),str))
    return true;
    else return false;
}

Dec* InitDec(int capacity)
{
    Dec *Array= (Dec*)malloc(sizeof(Dec));
    if(Array==NULL)
    {
        printf("InitDec malloc 申请失败\n");
        return NULL;
    }
    Array->size=0;
    Array->capacity=capacity;
    Array->a=(ElementType*)malloc(sizeof(ElementType)*capacity);
    if(Array->a==NULL)
    {
        printf("InitDec malloc array 申请失败\n");
        free(Array);
        return NULL;
    }
    return Array;
}

void InsertTail(Dec *Array, ElementType element)
{
    if(Array->size>= Array->capacity)
    {
        Array->capacity *= 2;
        ElementType *newPtr= realloc(Array->a,sizeof(ElementType)*Array->capacity);
        if(newPtr == NULL)
        {
            printf("扩容数组失败\n");
            Array->capacity /= 2;
            return;
        }
        Array->a= newPtr;
    }
    Array->a[Array->size++]=element;
}

ElementType* FindByElement(Dec *Array, ElementType element)
{
    for(int i=0; i<Array->size; i++)
    {
        if(Array->a[i]==element)
        return &Array->a[i];
    }
    return NULL;
}

void RemoveByIndex(Dec *Array, int index)
{
    if(index<0 || index >= Array->size)
    {
        printf("非法删除位置\n");
        return;
    }
    for(int i=index; i<Array->size; i++)
    {
        Array->a[i]= Array->a[i+1];
    }
    Array->size--;
}

void RemoveByArray(Dec *Array, ElementType element)
{
    for(int i=0; i<Array->size; i++)
    {
        if(Array->a[i]==element)
        {
            RemoveByIndex(Array,i);
            i--;
        }
    }
}

void PrintArray(Dec *Array, void(*Print)(ElementType) )
{
    printf("size:%d    capacity:%d\n",Array->size,Array->capacity);
    for(int i=0; i<Array->size; i++)
    {
        Print(Array->a[i]);
    }
    printf("\n");
}

void FreeArray(Dec *Array, void(*Free)(ElementType))
{
    if(Free)
    {   
        for(int i=0; i<Array->size; i++)
        {
            Free(Array->a[i]);
        }
    }
    free(Array->a);
    free(Array);
}

//插入的电话号码

Tel* InitTel(const char *name, const char *number)
{
    Tel *s=(Tel *)malloc(sizeof(Tel));
    if(s==NULL)
    {
        printf("InitTel malloc error\n");
        return NULL;
    }
    s->name=strdup(name);
    s->number=strdup(number);
    return s;
}

void RemoveTel(Dec *Array,void *data, bool (*IsEqual)(void *, void *))
{
    for(int i=0; i< Array->size; i++)
    {
        if(IsEqual(Array->a[i],data))
        {
            RemoveByIndex(Array,i);            
            i--;
        }
    }
    printf("删除成功");
}

Tel* FindTel(Dec *Array, void *data, bool (*IsEqual)(void *, void *))
{
    for(int i=0; i< Array->size;i++)
    {
        if(IsEqual(Array->a[i],data))
        {
            return Array->a[i];
        }
    }
    return NULL;
}

Tel* BinarySearch(Dec* Array, ElementType name,bool (*GreatName)(void *p1, void *p2),bool (*GreatName2)(void *p1, void *p2))
{
    int left=0;
    int right= Array->size-1;
    while(left<=right)
    {
        int mid= left+(right-left)/2;
        // int mid= (left & right) + ((left ^ right)>>1);
    
    if(GreatName(Array->a[mid],name))
        right= mid-1;

    else if(GreatName2(name,Array->a[mid]))
        left= mid+1;

    else
        return Array->a[mid];
    }
    return NULL;
}

Tel* Search(Dec *Array, ElementType name)
{
    return BinarySearch(Array, name, GreatName,GreatName2);
}

void FreeTel(void *ptr)
{
    Tel *s=(Tel *)ptr;
    free(s->name);
    free(s->number);
    free(s);
}

void PrintTel(void *ptr)
{
    Tel *s=(Tel *)ptr;
    printf("%s  %s\n",s->name,s->number);
}

void FastSort(ElementType *a, int start, int end, bool(*Compare)(ElementType, ElementType))
{
    if(start>=end)
    return;

    int left= start;
    int right= end;
    ElementType temp= a[left]; //将最左边的值定位基准值
    while(left<right)
    {
        //右边往左动找比基准值小的数
        while (Compare(a[right],temp) && left<right)
        right--;
            
            if(left<right)
            {
            a[left]=a[right];
            left++;
            }   //把右边的比基准值小的数，扔到左边
        
        
        //左边往右边动找比基准值大的数
        while (Compare(temp,a[left]) && left<right)
        left++;
            
            if(left<right)
            {
            a[right]= a[left]; //把左边的比基准值大的数扔到右边
            right--;
            }
    }
                a[left]=temp;
            FastSort(a,start,left-1,Compare);
            FastSort(a,right+1,end,Compare);
}

void Sort(Dec *a, bool(*Compare)(ElementType, ElementType))
{
    FastSort(a->a,0,a->size-1,Compare);
}